输出格式：

在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

1
2
3
4
5
6
7
8
9
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

输出样例

1
4 1 5

思路

首先，按照题目给的数据进行建树；然后，由于题目要求从上到下、从左到右地输出所有叶节点，所以只需要层序遍历就可以了，遍历到每个节点的时候判断是否为叶节点，叶节点就是左右子树都为空。另外需要注意的是，题目没有给出根节点是哪个点，所以需要自己找根节点，只需要判断谁没做过儿子就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
typedef struct node
{
    int l,r;
}Node;
Node T[maxn];
int n;
unordered_map<int,int> IsRoot;
vector<int> res;
int main()
{
    cin >> n;
    for(int i=0;i<n;i++){
        char l,r;
        cin >> l >> r;
        if(l == '-') T[i].l = -1;
        else{
            T[i].l = l - '0';
            IsRoot[l - '0'] = 1;
        }
        if(r == '-') T[i].r = -1;
        else {
            T[i].r = r - '0';
            IsRoot[r - '0'] = 1;
        }
    }
    int root = 0;
    for(int i=0;i<n;i++){
        if(!IsRoot.count(i)) root = i;
    }
    queue<int> q;
    q.push(root);
    while(q.size()){
        auto t = q.front();
        q.pop();
        if(T[t].l == -1 && T[t].r == -1){
            res.push_back(t);
        }else{
            if(T[t].l != -1) q.push(T[t].l);
            if(T[t].r != -1) q.push(T[t].r);
        }
    }
    for(int i=0;i<res.size();i++){
        if(i != 0) cout << " ";
        cout << res[i];
    }
    return 0;
}